from tools_algorithm import *


class Solution:
    def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:

        lp = len(pattern)
        next, cnt = [0] * lp, 0
        for i in range(1, lp):
            while cnt > 0 and pattern[i] != pattern[cnt]:
                cnt = next[cnt - 1]
            if pattern[i] == pattern[cnt]:
                cnt += 1
            next[i] = cnt

        def check(pj, ni):
            p = pattern[pj]
            if p == 1:
                return nums[ni + 1] > nums[ni]
            elif p == 0:
                return nums[ni + 1] == nums[ni]
            else:
                return nums[ni + 1] < nums[ni]

        j = 0
        ans = 0
        for i in range(0, len(nums) - 1):
            while j > 0 and not check(j, i):
                j = next[j - 1]
            if check(j, i):
                j += 1
            if j == lp:
                ans += 1
                j = next[j - 1]
        return ans


class Solution:
    def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:

        n = len(pattern)
        ha = 0
        mod = 1000000007
        z = 11
        for p in pattern:
            ha = ha * z + p + 2
            ha %= mod
        cha = 0

        def f(i):
            if nums[i + 1] > nums[i]:
                return 3
            elif nums[i + 1] == nums[i]:
                return 2
            return 1

        ans = 0
        for i in range(len(nums) - 1):
            if i >= n:
                cha = (cha - (f(i - n) * pow(z, n - 1, mod) % mod) + mod) % mod
            cha = (cha * z + f(i)) % mod
            if cha == ha:
                ans += 1
        return ans


s = Solution()
print(s.countMatchingSubarrays(nums=[1, 2, 3], pattern=[1, 1]) == 1)
print(
    s.countMatchingSubarrays(
        [
            120611938,
            120611938,
            120611938,
            120611938,
            120611938,
            120611938,
            120611938,
            78376769,
            78376769,
            78376769,
            78376769,
        ],
        [0, 0, 0],
    )
    == 5
)
print(
    s.countMatchingSubarrays(
        [645814052, 330048419, 645814052, 330048419, 160218431, 46882695],
        [-1, 1, -1, -1],
    )
    == 1
)
print(s.countMatchingSubarrays(nums=[1, 2, 3, 4, 5, 6], pattern=[1, 1]) == 4)
print(s.countMatchingSubarrays(nums=[1, 4, 4, 1, 3, 5, 5, 3], pattern=[1, 0, -1]) == 2)
